import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;



public class One_Two {

	public static void main(String[] args) {
	      Integer[] list=new Integer[5];
	      list[0]=4654;
	      list[1]=6;
	      list[2]=97987;
	      list[3]=3;
	      list[4]=6;//这里打乱顺序定义了一个数组，然后传进去实现排序的顺序表里面
	      SinglyLinkedList<Integer> a=new SinglyLinkedList<Integer>(list);
	      SinglyLinkedList<Integer> b=new SinglyLinkedList<Integer>(a);
	      a.showList();//输出顺序表，原本打乱的元素重新排序
	      a.add(10);//添加一个10，其位置由其值绝对
	      System.out.println();
	      a.showList();
	      System.out.println();
	      b.showList();
	      b.concat(a);//b和a连起来
	      System.out.println();
	      b.showList();
	      b.replace(8,6);//把第一个出现的8换成6
	      System.out.println();
	      b.showList();
	      System.out.println();
	      System.out.println(b.search(3).date);//找到3并返回
	      b.remove(0);//去掉3
	      b.showList();
	      System.out.println();
	      
	      
	      
	      
	      
	      
	      
	      

	}

}
class SinglyLinkedList<T extends Comparable> {
	
	Node<T> head = new Node<T>();
	int size=0;
	
	
	public SinglyLinkedList(T[] element) {
		
		List list=new ArrayList<T>();
		for(int i=0;i<element.length;i++) {
			list.add(element[i]);
		}
		Collections.sort(list);
		Node<T> p=this.head;
		for(int i=0;i<element.length;i++) {
			Node<T>node= new Node<T>((T) list.get(i),null);
		    p.next=node;
		    p=p.next;
		    size++;
		}
	}
	
	public SinglyLinkedList(SinglyLinkedList list) {
		Node<T> p=this.head;
		Node<T> q=list.head;
		while(q.next!=null) {
			Node<T> node=new Node<T>(q.next.date,q.next.next);
			p.next=node;
			q=q.next;
			p=p.next;
			size++;
		}
	}
	
	public SinglyLinkedList() {
		// TODO 自动生成的构造函数存根
	}

	public void concat(SinglyLinkedList list) {
		Node<T> p=this.head;
		Node<T> q=list.head;
		while(p.next!=null) {
			p=p.next;
		}
		while(q.next!=null) {
			Node<T> node=new Node<T>(q.next.date,q.next.next);
			p.next=node;
			p=p.next;
			q=q.next;
			size++;
		}
	}
	
	public T get(int i) {
		
		if(i<0||i>this.size){
			return null;
		}
		
		Node<T> p=this.head;
       
		for(int j=0;j<i;j++) {
			p=p.next;
		}
		return p.date;
	}
	
	public Node<T> search(T element){
		Node<T> p=this.head;
		while(p.next!=null) {
			Node<T> node=p.next;
			if(node.date.equals(element)) {
				return node;
			}
			p=p.next;
			
		}
		
		return null;
	}

	public boolean contain(T element) {
		if (search(element)!=null) {
			return true;
		}
		return false;
	}
	
	
	
	public boolean remove(int i) {
		if(i>this.size||i<0)
			return false;
		Node<T> p=this.head;
		for(int j=0;j<i;j++) {
			p=p.next;
		}
		
		p.next=p.next.next;
		
		
		size--;
		
		return true;
	}
	
	public boolean add(T element) {
		Node<T> p=this.head;
		Node<T> q=new Node<T>(element,null);
		while(p.next!=null&&p.next.date.compareTo(element)!=1) {
			p=p.next;
		}
		if(p.next==null) {
			p.next=q;
		}
		else {
		q.next=p.next;
		p.next=q;
		}
		return true;
	}
	
	public void showList() {
		Node<T> p=this.head;
		while(p.next!=null) {
			System.out.print(p.next.date+" ");
		    p=p.next;
		}
	}
	
	public boolean replace(Object obj, T element) {
		Node<T> t=new Node<T>((T)obj,null);
		if(!contain(element)) {
			return false;
		}
		Node<T> p=this.head;
		while(p.next!=null&&!p.next.date.equals(element)) {
			p=p.next;
		}
		t.next=p.next.next;
		p.next=t;
		return true;
		
	}
	
	public boolean equals(Object obj) {
		
		SinglyLinkedList<T> tlist=(SinglyLinkedList<T>)obj;
		if(tlist.size!=this.size)
			return false;
		Node<T> p=this.head;
		Node<T> q=tlist.head;
		while(p.next!=null) {
			Node<T> node=p.next;
			Node<T> node1=q.next;
			if(!node.date.equals(node1.date)){
				return false;
			}
			p=p.next;
			q=q.next;
			
		}
		return true;
		
	}
	
	public Iterator2<T> iterator(){
		return new Itr();
	}
	 public class Itr implements Iterator2<T> 
	{
		 int cursor=0;      
	     ArrayList<T>list=new ArrayList<T>();
	     int number=size;
	     public Itr() {
	    	 for(int i=1;i<=size;i++) {
	    		 list.add(get(i));
	    	 }
	     }
		@Override
		public boolean hasNext() {
			// TODO 自动生成的方法存根
			 return cursor != number;//当cursor不等于size时，表示仍有索引元素
		}

		@Override
		public T next() {
			
			return list.get(cursor++);
			
		}
		
		public void remove() {
			int o=cursor-1;
			SinglyLinkedList.this.remove(o);
		
		}
		//返回指定对象首次出现位置，若未找到返回-1
		public int indexOf(Object obj) {
			
			return list.indexOf(obj);
			
		}
	
		@Override
		public boolean equals2(SinglyLinkedList obj) {
			Iterator2 it=obj.iterator();
			for(int i=0;i<list.size();i++) {
				if(list.get(i).compareTo(it.next())!=0) {
					return false;
				}
			}
			
		    
			
			
			
			
			
			return true;
			
		}
		 
	 }
	
	
	

	
		
	
	
}

